<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // NO.1 寻找两个正序数组的中位数
      //给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
      //算法的时间复杂度应该为 O(log (m+n)) 。
      // 示例 1：
      // 输入：nums1 = [1,3], nums2 = [2]
      // 输出：2.00000
      // 解释：合并数组 = [1,2,3] ，中位数 2

      // 示例 2：
      // 输入：nums1 = [1,2], nums2 = [3,4]
      // 输出：2.50000
      // 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

      // 示例 3：
      // 输入：nums1 = [0,0], nums2 = [0,0]
      // 输出：0.00000

      // 示例 4：
      // 输入：nums1 = [], nums2 = [1]
      // 输出：1.00000

      // 示例 5：
      // 输入：nums1 = [2], nums2 = []
      // 输出：2.00000

      // 低配解法，合并排序新数组，取出中位值：
      // var findMedianSortedArrays = function (nums1, nums2) {
      //   let result = 0
      //   let arr = [...nums1, ...nums2].sort((a, b) => {
      //     return a - b
      //   })
      //   if (arr.length % 2 == 0) {
      //     //偶数
      //     result = (
      //       (arr[arr.length / 2] + arr[arr.length / 2 - 1]) /
      //       2
      //     ).toFixed(5)
      //   } else {
      //     result = arr[parseInt(arr.length / 2)].toFixed(5)
      //   }
      //   return result
      // }

      // 双指针法：
      // 因为两个数组有序，求中位数不需要把两个数组合并
      // 当合并后的数组总长度len为奇数时，只要知道索引为len/2位置上的数就行了，如果数偶数，只要知道索引为len/2 - 1和len/2上的数就行，所以不管是奇数还是偶数只要遍历len/2次即可，
      // 用两个值来存遍历过程中len/2-1和len/2上的数即可
      // 两个指针point1和point2分别指向nums1和nums2，当nums1[point1] < nums2[point2]，则point1指针移动，否则point2指针移动
      // var findMedianSortedArrays = function (nums1, nums2) {
      //   debugger
      //   let n1 = nums1.length
      //   let n2 = nums2.length

      //   // 两个数组总长度
      //   let len = n1 + n2

      //   // 保存当前移动的指针的值(在nums1或nums2移动)，和上一个值
      //   let preValue = -1
      //   let curValue = -1

      //   //  两个指针分别在nums1和nums2上移动
      //   let point1 = 0
      //   let point2 = 0

      //   // 需要遍历len/2次，当len是奇数时，最后取curValue的值，是偶数时，最后取(preValue + curValue)/2的值
      //   for (let i = 0; i <= Math.floor(len / 2); i++) {
      //     preValue = curValue
      //     // 需要在nums1上移动point1指针
      //     if (point1 < n1 && (point2 >= n2 || nums1[point1] < nums2[point2])) {
      //       curValue = nums1[point1]
      //       point1++
      //     } else {
      //       curValue = nums2[point2]
      //       point2++
      //     }
      //   }

      //   return len % 2 === 0 ? (preValue + curValue) / 2 : curValue
      // }
    </script>
  </body>
</html>
